一、GATNE [2019]

《Representation Learning for Attributed Multiplex Heterogeneous Network》

1. network embedding 或 network representation learning 是一种很有前途的方法，可以将网络中的节点投影到低维连续的空间，同时保持网络结构和固有属性。由于network embedding 推动了节点分类、链接预测、社区检测等下游 network learning 的重大进展，因此它最近引起了人们的极大关注。DeepWalk, LINE, node2vec 是将深度学习技术引入网络分析从而学习 node embedding 的开创性工作。NetMF 对不同 network embedding 算法的等价性（equivalence） 进行了理论分析，而随后的 NetSMF 通过稀疏化给出了可扩展的解决方案。然而，它们被设计为仅处理具有单一类型节点和边的同质网络（homogeneous network） 。

   最近，人们针对异质网络提出了 PTE, metapath2vec, HERec。然而，现实世界的网络应用（例如，电商）要复杂得多，不仅包含多种类型的节点和边，还包含一组丰富的属性。由于 embedding learning 的重要性和挑战性，已有大量工作尝试来研究复杂网络的 embedding learning 。根据网络拓扑（同质的或异质的）、属性（带属性或不带属性），论文《Representation Learning for Attributed Multiplex Heterogeneous Network》对六种不同类型的网络进行了分类，并在下表中总结了它们的相对进展。这六个类别包括：同质网络（Homogeneous Network: HON）、属性同质网络（Attributed Homogeneous Network: AHON）、异质网络 （Heterogeneous Network: HEN）、属性异质网络 （Attributed Heterogeneous Network: AHEN）、多重异质网络 （Multiplex Heterogeneous Network: MHEN）、属性多重异质网络 （Attributed Multiplex Heterogeneous Network: AMHEN）。可以看到，人们对 AMHEN 的研究最少。

   

   在论文《Representation Learning for Attributed Multiplex Heterogeneous Network》中，作者专注于 AMHEN 的 embedding learning，其中不同类型的节点可能与多种不同类型的边相连接，而且每个节点可能关联一组不同的属性。这在许多online application 中很常见。例如，在论文使用的四个数据集中，Twitter 有 20.3%、YouTube 有 21.6%、Amazon 有 15.1%、Alibaba 有 16.3% 的边具有不止一种类型。例如，在电商系统中，用户可能与item 进行多种类型的交互，如点击（click ）、转化（conversion） 、加购物车 （add-to-cart ）、收藏 （add-to-preference ）。下图说明了这样的一个例子。显然， user 和 item 具有本质上不同的属性，不应该一视同仁。此外，不同类型的 user-item 交互意味着不同程度的兴趣，应该区别对待。否则，系统无法准确捕获用户的行为模式（behavioral pattern ）和偏好，因此无法满足实际使用的需求。

   下图中，左侧的用户和属性相关联，用户属性包括性别、年龄、地域；右侧的item 也和属性相关联，item 属性包括价格、品牌等。 user-item 之间的边有四种类型：点击、加购物车、收藏、转化（即购买）。中间的三个子图代表三种建模方式，从上到下依次为 HON, MHEN, AMHEN 。最右侧给出了在阿里巴巴数据集上不同模型相对于 DeepWalk 性能的提升。可以看到，GATNE-I 相比 DeepWalk 提升了 28.23% 。

   

   不仅因为异质性（heterogeneity） 和多重性 （multiplicity ），在实践中处理 AMHEN 带来了几个独有的挑战：

   • 多重边 （multiplex edge）：每对节点 pair 对之间可以存在多种不同类型的关系，因此结合不同类型关系并学习统一的 embedding 非常重要。

   • 部分观测 （partial observation）：真实网络的数据实际上只有部分被观测到。如，一个长尾用户可能只与某些商品产生很少的交互。现有的大部分 network embedding 方法仅关注于 transductive 场景，因此无法解决长尾或冷启动问题。

   • 可扩展性（scalability）：真实网络通常具有数十亿个节点、数百亿甚至千亿的边。因此模型的可扩展性非常重要。

   为应对上述挑战，论文《Representation Learning for Attributed Multiplex Heterogeneous Network》提出了一种新颖的方法来捕获丰富的属性信息，并利用来自不同节点类型的多重拓扑结构（multiplex topological structure ），即通用属性多重异质网络嵌入 （General Attributed Multiplex HeTerogeneous Network Embedding: GATNE）。GATNE 的主要特性如下：

   • 作者正式定义了 attributed multiplex heterogeneous network embedding 问题，这是现实世界网络的更通用的representation 。

   • GATNE 同时支持 attributed multiplex heterogeneous network 的 transductive embedding learning 和 inductive embedding learning 。论文还给出了理论分析，从而证明所提出的 transductive 模型比现有模型（如 MNE 更通用）。

   • 论文为 GATNE 开发了高效且可扩展的学习算法，从而能够有效地处理数亿个节点和数十亿条边。

   论文进行了广泛的实验，从而在四种不同类型的数据集（Amazon, YouTube, Twitter, Alibaba）上评估所提出的模型。实验结果表明：与 SOTA 方法相比，论文的方法可以实现显著的提升。作者已经在阿里巴巴的分布式系统上部署了所提出的模型，并将该方法应用到了阿里巴巴的推荐引擎中。离线 A/B test 进一步证实了论文所提出方法的效果和效率。

2. 相关工作：这里我们回顾了 network embedding、heterogeneous network embedding、multiplex heterogeneous network embedding、attributed network embedding 相关的 SOTA 方法。

   • Network Embedding：network embedding 方面的工作主要包括两类，graph embedding: GE、graph neural network: GNN。

     GE 的代表工作包括：

     • DeepWalk 方法通过随机游走在图上生成语料库，然后在语料库上训练 SkipGram 模型。

     • LINE 学习大型网络上的 node representation，同时保持一阶邻近性和二阶邻近性。

     • node2vec 设计了一个有偏的随机游走程序来有效地探索不同类型的邻域。

     • NetMF 是一个统一的矩阵分解框架，用于从理论上理解和改进 DeepWalk, LINE 。

     GNN 中的热门工作包括：

     • GCN （《Semi-Supervised Classification with Graph Convolutional Networks》） 使用卷积运算将邻域的 feature representation 融合到当前节点的 feature representation 中。

     • GraphSAGE 提供了一种将网络结构信息和节点特征相结合的 inductive 方法。GraphSAGE 学习 representation 函数而不是每个节点的直接 embedding，这有助于它可以应用到训练期间 unseen 的节点。

   • Heterogeneous Network Embedding ：异质网络包含各种类型的节点和/或边。众所周知，由于异质内容和结构的各种组合，这类网络很难挖掘。目前人们在嵌入动态的、异质的大型网络方面所作的努力有限。

     • HNE 共同考虑网络中的内容和拓扑结构，将异质网络中的不同对象表示为统一的向量 representation 。

     • PTE 从label 信息和不同级别的 word co-occurrence 信息中构建大型异质文本网络，然后将其嵌入到低维空间中。

     • metapath2vec 通过 metapath-based 随机游走来构建节点的异质邻域，然后利用异质 SkipGram 模型来执行 node embedding 。

     • HERec 使用 metapath-based 随机游走策略来生成有意义的节点序列从而学习 network embedding 。这些 embedding 首先通过一组融合函数进行变换，然后集成到扩展的矩阵分解模型中。

   • Multiplex Heterogeneous Network Embedding：现有方法通常研究节点之间具有单一类型邻近关系（proximity） 的网络，它仅捕获网络的单个视图。然而，在现实世界中，节点之间通常存在多种类型的临近关系，产生具有多个视图的网络。

     • PMNE 提出了三种将多重网络投影到连续向量空间的方法。

     • MVE 使用注意力机制将多视图网络嵌入到单个协同的 embedding 中。

     • MNE 对每个节点使用一个 common embedding 以及若干个 additional embedding ，其中每种类型的边对应一个 additional embedding 。这些 embedding 由一个统一的 network embedding 模型来共同学习。

     • mvn2vec 探索了通过同时建模 preservation 和 collaboration 以分别表示不同视图中边语义（ edge semantic meaning ）从而实现更好的 embedding 结果的可行性。

   • Attributed Network Embedding：属性网络旨在为网络中的节点寻找低维向量 representation，以便在 representation 中同时保持原始网络拓扑结构和节点属性邻近性。

     • TADW 在矩阵分解框架下，将节点的文本特征融入 network representation learning 中。

     • LANE 将 label 信息平滑地融合到属性网络 embedding 中，同时保持节点的相关性。

     • AANE 能够以分布式方式完成联合学习过程，从而加速属性网络 embedding 。

     • SNE 提出了一个通用框架，通过捕获结构邻近性和属性邻近性来嵌入社交网络。

     • DANE 可以捕获高度非线性并保持拓扑结构和节点属性中的各种邻近性。

     • ANRL 使用邻域增强自编码器对节点属性信息进行建模，并使用基于属性编码器和属性感知 SkipGram 模型来捕获网络结构。

1.1 模型

1.1.1 基本概念

1. 给定图 $\mathcal{G}=(\mathcal{V},\mathcal{E})$$\mathcal G=(\mathcal V,\mathcal E)$ ，其中 $\mathcal{V}$$\mathcal V$ 为节点集合 $\mathcal{V}=\{v_1,\cdots ,v_n\}$$\mathcal V=\{v_1,\cdots,v_n\}$ ，$\mathcal{E}$$\mathcal E$ 为边的集合 $\mathcal{E}=\{e_{i,j}\}$$\mathcal E=\{e_{i,j}\}$ 。每条边 $e_{i,j}=(v_i,v_j)$$e_{i,j} = (v_i,v_j)$ 都有一个权重 $w_{i,j}\ge 0$$w_{i,j}\ge 0$ ，它表示节点 $v_i$$v_i$ 和 $v_j$$v_j$ 的关系强度。

   $\mathcal{G}$$\mathcal G$ 可以为有向图，而也可以为无向图。对于无向图有 $e_{i,j}=e_{j,i}$$e_{i,j} = e_{j,i}$ 和 $w_{i,j}=w_{j,i}$$w_{i,j} = w_{j,i}$ ，对于有向图则有 $e_{i,j}\ne e_{j,i}$$e_{i,j} \ne e_{j,i}$ 和 $w_{i,j}\ne w_{j,i}$$w_{i,j} \ne w_{j,i}$ 。

2. 异质网络（Heterogeneous Network） 定义：一个异质网络 $\mathcal{G}=(\mathcal{V},\mathcal{E})$$\mathcal G=(\mathcal V,\mathcal E)$ 关联一个节点类型映射函数 ：$\varphi :\mathcal{V}\to \mathcal{O}$$\phi:\mathcal V\rightarrow \mathcal O$ ，以及一个边类型映射函数：$\psi :\mathcal{E}\to \mathcal{R}$$\psi:\mathcal E\rightarrow \mathcal R$ ，其中 $\mathcal{O}$$\mathcal O$ 和 $\mathcal{R}$$\mathcal R$ 代表所有节点类型的集合和所有边类型的集合。每个节点 $v\in \mathcal{V}$$v\in \mathcal V$ 属于某个节点类型，每条边 $e\in \mathcal{E}$$e\in \mathcal E$ 属于某个边类型。如果 $|\mathcal{O}|+|\mathcal{R}|>2$$|\mathcal O| + |\mathcal R|\gt 2$，则这个网络被称作是异质的（heterogeneous） ，否则是同质的（ homogeneous ）。

   对于异质网络，考虑到节点 $v_i,v_j$$v_i,v_j$ 之间可能存在多条边，每条边属于不同的类型。因此我们标记边为 $e_{i,j}^{(r)}$$e_{i,j}^{(r)}$，它表示 $v_i$$v_i$ 和 $v_j$$v_j$ 之间类型为 $r\in \mathcal{R}$$r\in \mathcal R$ 的边。

3. 属性网络（Attributed Network） 定义：一个属性网络 $\mathcal{G}=(\mathcal{V},\mathcal{E},\mathcal{A})$$\mathcal G=(\mathcal V,\mathcal E, \mathcal A)$ ，其中每个节点 $v_i\in \mathcal{V}$$v_i\in \mathcal V$ 关联一个属性向量 ${\overrightarrow{\mathbf{x}}}_i$$\mathbf{\vec x}_i$ 。 $\mathcal{A}$$\mathcal A$ 为所有节点的属性集合： $\mathcal{A}=\{{\overrightarrow{\mathbf{x}}}_i\mid v_i\in \mathcal{V}\}$$\mathcal A=\{\mathbf{\vec x}_i\mid v_i\in \mathcal V\}$ 。

4. 属性多重异质网络（Attributed Multiplex Heterogeneous Network: AMHEN）定义：一个属性多重异质网络 $\mathcal{G}=(\mathcal{V},\mathcal{E},\mathcal{A})$$\mathcal G=(\mathcal V,\mathcal E,\mathcal A)$ ，其中 $\mathcal{E}={\cup }_{r\in \mathcal{R}}{\mathcal{E}}_r$$\mathcal E=\cup_{r\in \mathcal R} \mathcal E_r$ ， ${\mathcal{E}}_r$$\mathcal E_r$ 由所有类型为 $r$$r$ 的边组成，并且 $|\mathcal{R}|>1$$|\mathcal R| \gt 1$ 。我们根据边的类型将图 $\mathcal{G}$$\mathcal G$ 拆分为独立的多个视图：${\mathcal{G}}_r=(\mathcal{V},{\mathcal{E}}_r,\mathcal{A})$$\mathcal G_r = (\mathcal V,\mathcal E_r,\mathcal A)$ 。

5. AMHEN Embedding 问题：给定一个 AMHEN 网络 $\mathcal{G}=(\mathcal{V},\mathcal{E},\mathcal{A})$$\mathcal G=(\mathcal V,\mathcal E,\mathcal A)$，对每种边的类型 $r\in \mathcal{R}$$r\in \mathcal R$ ，学习每个节点的低维 embedding 。即，对每种边类型 $r$$r$ ，找到函数 $f_r:\mathcal{V}\to {\mathbb{R}}^d$$f_r:\mathcal V\rightarrow \mathbb R^d$ ，其中 $d\ll |\mathcal{V}|$$d\ll |\mathcal V|$ 。

   对节点 $v_i$$v_i$，这里为每个视图 $r\in \mathcal{R}$$r\in \mathcal R$ 学习一个 embedding ，而不是所有视图共享一个 embedding 。这有两个好处：

   • 首先，可以通过各个视图的 embedding 来聚合得到一个所有视图共享的 embedding。

   • 其次，各个视图的 embedding 保持了各个视图的语义，因此可以用于 view-level 的任务，例如某个视图下的链接预测。

6. 我们首先在 transductive 上下文中提出 GATNE 框架，对应的模型称作 GATNE-T 。我们还将 GATNE-T 与新的流行模型（如 MNE）之间的联系进行了讨论。

   为解决部分观测（partial observation） 问题，我们进一步将模型扩展到 inductive 上下文中，并提出了 GATNE-I 模型。针对这两个模型，我们还提出了有效的优化算法。

1.1.2 GATNE-T

1. 在 transductive 环境中，我们将给定节点 $v_i$$v_i$ 在关于边类型 $r$$r$ 的 overall embedding 拆分为两个部分，如下图所示：

   • base embedding：节点 $v_i$$v_i$ 的 base embedding 在节点的不同边类型之间共享。

   • edge embedding：节点 $v_i$$v_i$ 在视图 ${\mathcal{G}}_r$$\mathcal G_r$ 上 embedding 。

   

2. 现在考虑 edge embedding 。类似于 GraphSage，我们假设节点 $v_i$$v_i$ 在 ${\mathcal{G}}_r$$\mathcal G_r$ 上的 embedding 一共有 $K$$K$ 层，第 $1\le k\le K$$1 \le k \le K$ 层 embedding 为：

   $${\overrightarrow{\mathbf{u}}}_{i,r}^{(k)}=\text{agg}\left(\{{\overrightarrow{\mathbf{u}}}_{j,r}^{(k-1)}\mid v_j\in {\mathcal{N}}_{i,r}\}\right)$$

   其中：

   • ${\mathcal{N}}_{i,r}$$\mathcal N_{i,r}$ 为节点 $v_i$$v_i$ 在视图 ${\mathcal{G}}_r$$\mathcal G_r$ 上的邻居节点集合。

   • agg 为一个聚合函数。类似于 GraphSAGE，它可以为均值聚合：

     $${\overrightarrow{\mathbf{u}}}_{i,r}^{(k)}=\sigma \left({\hat{\mathbf{W}}}^{(k)}\text{mean}\left(\{{\overrightarrow{\mathbf{u}}}_{j,r}^{(k-1)}\mid v_j\in {\mathcal{N}}_{i,r}\}\right)\right)$$

     也可以为池化聚合，如最大池化：

     $${\overrightarrow{\mathbf{u}}}_{i,r}^{(k)}=max\left(\{\sigma ({\hat{\mathbf{W}}}_{pool}^{(k)}{\overrightarrow{\mathbf{u}}}_{j,r}^{(k-1)}+\hat{{\overrightarrow{\mathbf{b}}}_{pool}^{(k)}})\mid v_j\in {\mathcal{N}}_{i,r}\}\right)$$

     其中 $\sigma (\cdot )$$\sigma(\cdot)$ 为激活函数。

   • ${\overrightarrow{\mathbf{u}}}_{i,r}^{(0)}$$\mathbf{\vec u}_{i,r}^{(0)}$ 在 transductive 模型中通过随机初始化。

   第 K 层 embedding ${\overrightarrow{\mathbf{u}}}_{i,r}^{(K)}$$\mathbf{\vec u}_{i,r}^{(K)}$ 为节点 $v_i$$v_i$ 的 embedding ${\overrightarrow{\mathbf{u}}}_{i,r}$$\mathbf{\vec u}_{i,r}$ 。我们拼接节点 $v_i$$v_i$ 所有的类型 $r$$r$ 的 embedding 得到节点 $v_i$$v_i$ 的 embedding 矩阵：

   $${\mathbf{U}}_i=({\overrightarrow{\mathbf{u}}}_{i,1},\cdots ,{\overrightarrow{\mathbf{u}}}_{i,|\mathcal{R}|})\in {\mathbb{R}}^{s\times |\mathcal{R}|}$$

   其中 $s$$s$ 为 edge embedding 的维度， $|\mathcal{R}|$$|\mathcal R|$ 为边的类型数量。

   进一步地，我们使用 self-attention 机制来计算加权系数 ${\overrightarrow{\mathbf{a}}}_{i,r}$$\mathbf{\vec a}_{i,r}$ ，从而线性组合 $\{{\overrightarrow{\mathbf{u}}}_{i,1},\cdots ,{\overrightarrow{\mathbf{u}}}_{i,|\mathcal{R}|}\}$$\{\mathbf{\vec u}_{i,1},\cdots,\mathbf{\vec u}_{i,|\mathcal R|}\}$ ，得到节点 $v_i$$v_i$ 的 edge embedding ：

   $$\begin{array}{c}{\overrightarrow{\mathbf{a}}}_{i,r}=\text{softmax}({\overrightarrow{\mathbf{w}}}_r^{\mathrm{\top }}\tanh ({\mathbf{W}}_r{\mathbf{U}}_i){)}^{\mathrm{\top }}\in {\mathbb{R}}^{|\mathcal{R}|}\\ {\widehat{\overrightarrow{\mathbf{u}}}}_{i,r}={\mathbf{U}}_i{\overrightarrow{\mathbf{a}}}_{i,r}\in {\mathbb{R}}^s\end{array}$$

   其中：

   • ${\overrightarrow{\mathbf{w}}}_r\in {\mathbb{R}}^{d_a}$$\mathbf{\vec w}_r\in \mathbb R^{d_a}$ 和 ${\mathbf{W}}_r\in {\mathbb{R}}^{d_a\times s}$$\mathbf W_r\in \mathbb R^{d_a\times s}$ 都是针对边类型 $r$$r$ 的参数。

   • ${\widehat{\overrightarrow{\mathbf{u}}}}_{i,r}$$\hat{\mathbf{\vec u}}_{i,r}$ 为最终节点 $v_i$$v_i$ 在节点类型为 $r$$r$ 上的 edge embedding 。

   注意，这里在每种节点类型上都计算一个 self-attention，而并不是所有节点类型共享同一个 self-attention。

3. 假设节点 $v_i$$v_i$ 的 base embedding 为 ${\overrightarrow{\mathbf{b}}}_i\in {\mathbb{R}}^d$$\mathbf{\vec b}_i\in \mathbb R^d$，节点 $v_i$$v_i$ 在视图 ${\mathcal{G}}_r$$\mathcal G_r$ 上的 embedding 为 ${\widehat{\overrightarrow{\mathbf{u}}}}_{i,r}={\mathbf{U}}_i{\overrightarrow{\mathbf{a}}}_{i,r}$$\hat{\mathbf{\vec u}}_{i,r} = \mathbf U_i \mathbf{\vec a}_{i,r}$ 。则节点 $v_i$$v_i$ 在边类型为 $r$$r$ 上的 overall embedding 为：

   $${\overrightarrow{\mathbf{v}}}_{i,r}={\overrightarrow{\mathbf{b}}}_i+{\alpha }_r{\mathbf{M}}_r^{\mathrm{\top }}{\widehat{\overrightarrow{\mathbf{u}}}}_{i,r}={\overrightarrow{\mathbf{b}}}_i+{\alpha }_r{\mathbf{M}}_r^{\mathrm{\top }}{\mathbf{U}}_i{\overrightarrow{\mathbf{a}}}_{i,r}$$

   其中：

   • ${\mathbf{M}}_r\in {\mathbb{R}}^{s\times d}$$\mathbf M_r\in \mathbb R^{s\times d}$ 为一个线性映射的转化矩阵，用于将 edge embedding 映射到和 base embedding 的同一空间。

   • ${\alpha }_r$$\alpha_r$ 为超参数，用于平衡 base embedding 和 edge embedding 的重要性。

     令 $\widetilde{{\mathbf{M}}_r}={\alpha }_r\times {\mathbf{M}}_r$$\tilde{\mathbf M_r} = \alpha_r\times \mathbf M_r$，则通过学习参数 ${\tilde{\mathbf{M}}}_r$$\tilde{\mathbf M}_r$ 就相当于间接学习了 ${\alpha }_r$$\alpha_r$ 和 ${\mathbf{M}}_r$$\mathbf M_r$ 。因此这里的 ${\alpha }_r$$\alpha_r$ 似乎没有必要？

     另外，这里 embedding 训练的目标是什么？要保持什么属性？论文都未提及。根据论文的示意图，猜测是用异质 SoftMax 保持一阶邻近性。

1.1.2 GATNE vs MNE

1. 这里我们讨论 GATNE-T 和 MNE 的关系。在 GATNE-T 中，我们使用 attention 机制来捕获不同边类型之间的影响因子。我们从理论上证明，GATNE-T 是 MNE 的更为泛化的形式，可以提高模型的表达能力。

2. 在 MNE 模型中，节点 $v_i$$v_i$ 在类型 $r$$r$ 的边上的 overall embedding 为：

   $${\widetilde{\overrightarrow{\mathbf{v}}}}_{i,r}={\overrightarrow{\mathbf{b}}}_i+{\alpha }_r{\mathbf{X}}_r^{\mathrm{\top }}{\overrightarrow{\mathbf{o}}}_{i,r}$$

   其中 ${\mathbf{X}}_r$$\mathbf X_r$ 为类型 $r$$r$ 的边采用的映射矩阵。

   相比之下，GATNE-T 中，节点 $v_i$$v_i$ 在边类型为 $r$$r$ 上的 overall embedding 为：

   $${\overrightarrow{\mathbf{v}}}_{i,r}={\overrightarrow{\mathbf{b}}}_i+{\alpha }_r{\mathbf{M}}_r^{\mathrm{\top }}{\mathbf{U}}_i{\overrightarrow{\mathbf{a}}}_{i,r}={\overrightarrow{\mathbf{b}}}_i+{\alpha }_r{\mathbf{M}}_r^{\mathrm{\top }}\sum _{p=1}^{|\mathcal{R}|}{\lambda }_p{\overrightarrow{\mathbf{u}}}_{i,p}$$

   其中 ${\lambda }_p$$\lambda_p$ 为 ${\overrightarrow{\mathbf{a}}}_{i,r}$$\mathbf{\vec a}_{i,r}$ 的第 $p$$p$ 个元素，并且计算为：

   $${\lambda }_p=\frac{\exp ({\overrightarrow{\mathbf{w}}}_r^{\mathrm{\top }}\tanh ({\mathbf{W}}_r{\overrightarrow{\mathbf{u}}}_{i,p}))}{\sum _{t=1}^{|\mathcal{R}|}\exp ({\overrightarrow{\mathbf{w}}}_r^{\mathrm{\top }}\tanh ({\mathbf{W}}_r{\overrightarrow{\mathbf{u}}}_{i,t}))}$$

3. 定理：对于任意 $r\in \mathcal{R}$$r\in \mathcal R$，存在参数 ${\overrightarrow{\mathbf{w}}}_r$$\mathbf{\vec w}_r$ 以及 ${\mathbf{W}}_r$$\mathbf W_r$，使得对于任意 ${\overrightarrow{\mathbf{o}}}_{i,1},\cdots ,{\overrightarrow{\mathbf{o}}}_{i,|\mathcal{R}|}\in {\mathbb{R}}^s$$\mathbf{\vec o}_{i,1},\cdots,\mathbf{\vec o}_{i,|\mathcal R|}\in \mathbb R^s$ 以及对应的 ${\mathbf{X}}_r\in {\mathbb{R}}^{s\times d}$$\mathbf X_r\in \mathbb R^{s\times d}$，存在 ${\overrightarrow{\mathbf{u}}}_{i,1},\cdots ,{\overrightarrow{\mathbf{u}}}_{i,|\mathcal{R}|}\in {\mathbb{R}}^{s+|\mathcal{R}|}$$\mathbf{\vec u}_{i,1},\cdots,\mathbf{\vec u}_{i,|\mathcal R|}\in \mathbb R^{s+|\mathcal R|}$ 以及对应的 ${\mathbf{M}}_r\in {\mathbb{R}}^{(s+|\mathcal{R}|)\times d}$$\mathbf M_r\in \mathbb R^{(s+|\mathcal R|)\times d}$，满足 ${\overrightarrow{\mathbf{v}}}_{i,r}\simeq {\widetilde{\overrightarrow{\mathbf{v}}}}_{i,r}$$\mathbf{\vec v}_{i,r}\simeq \tilde{\mathbf{\vec v}}_{i,r}$ 。

   证明见原始论文。

   因此，GATNE-T 的模型空间几乎包含了 MNE 的模型空间。

1.1.3 GATNE-I

1. GATNE-T 的局限性在于它无法处理未观测数据。实际很多应用中，我们获得的数据只是部分观测的。这里我们将模型扩展到 inductive 环境中，并提出了 GATNE-I 。

   • 我们将节点 $v_i$$v_i$ 的 base embedding ${\overrightarrow{\mathbf{b}}}_i$$\mathbf{\vec b}_i$ 定义为节点属性 ${\overrightarrow{\mathbf{x}}}_i$$\mathbf{\vec x}_i$ 的函数：

     $${\overrightarrow{\mathbf{b}}}_i=h_z({\overrightarrow{\mathbf{x}}}_i)$$

     其中 $h_z$$h_z$ 为一个映射函数，并且 $z=\varphi (i)$$z=\phi(i)$ 为节点 $v_i$$v_i$ 对应的类型。

     即，不同类型的节点采用不同类型的映射函数。

     注意：不同类型的节点可能具有不同维度的属性 ${\overrightarrow{\mathbf{x}}}_i$$\mathbf{\vec x}_i$ 。函数 $h_z$$h_z$ 可能具有不同的形式，如多层感知机。

   • 类似地，节点 $i$$i$ 对于边类型 $r$$r$ 的初始 edge embedding ${\overrightarrow{\mathbf{u}}}_{i,r}^{(0)}$$\mathbf{\vec u}_{i,r}^{(0)}$ 也可以视为 ${\overrightarrow{\mathbf{x}}}_i$$\mathbf{\vec x}_i$ 的函数：

     $${\overrightarrow{\mathbf{u}}}_{i,r}^{(0)}=g_{z,r}({\overrightarrow{\mathbf{x}}}_i)$$

     其中 $g_{z,r}$$g_{z,r}$ 也是一个映射函数，将节点 $v_i$$v_i$ 的属性转换为边类型 $r$$r$ 的 edge embedding，其中 $z$$z$ 为节点 $v_i$$v_i$ 的节点类型。

   • 进一步地，在 inductive 环境下，我们为最终的 overall embedding 添加了一个额外的属性项：

     $${\overrightarrow{\mathbf{v}}}_{i,r}=h_z({\overrightarrow{\mathbf{x}}}_i)+{\alpha }_r{\mathbf{M}}_r^{\mathrm{\top }}{\mathbf{U}}_i{\overrightarrow{\mathbf{a}}}_{i,r}+{\beta }_r{\mathbf{D}}_z^{\mathrm{\top }}{\overrightarrow{\mathbf{x}}}_i$$

     其中 ${\beta }_r$$\beta_r$ 为平衡系数，${\mathbf{D}}_z$$\mathbf D_z$ 为节点类型为 $z$$z$ 的属性映射矩阵。

2. GATNE-T 仅使用网络结构信息，而 GATNE-I 考虑了网络结构信息和节点属性信息。我们采用异质 SkipGram 算法，它的输出层给出了一组多项式分布，每个分布对应于输入节点 $v$$v$ 的邻域的每种节点类型。

   如下图所示，这里有三种类型的节点（红色、绿色、蓝色）、两种类型的边（蓝色、橙色）。节点集合 $\mathcal{V}={\mathcal{V}}_1\cup {\mathcal{V}}_2\cup {\mathcal{V}}_3$$\mathcal V=\mathcal V_1\cup \mathcal V_2\cup \mathcal V_3$ ， $K_1,K_2,K_3$$K_1,K_2,K_3$ 分别为节点 $v$$v$ 的不同节点类型的邻域大小。

   

3. GATNE-T 和 GATNE-I 的区别主要在于 base embedding ${\overrightarrow{\mathbf{b}}}_i$$\mathbf{\vec b}_i$ 和初始 edge embedding ${\overrightarrow{\mathbf{u}}}_{i,r}^{(0)}$$\mathbf{\vec u}_{i,r}^{(0)}$ 的生成方式。

   • 在 transductive 的 GATNE-T 中，每个节点的 base embedding ${\overrightarrow{\mathbf{b}}}_i$$\mathbf{\vec b}_i$ 和初始 edge embedding ${\overrightarrow{\mathbf{u}}}_{i,r}^{(0)}$$\mathbf{\vec u}_{i,r}^{(0)}$ 基于网络结构来直接训练，并且 GATNE-T 无法处理训练期间未曾见过的节点。

   • 在 inductive 的 GATNE-I 中，每个节点的 base embedding ${\overrightarrow{\mathbf{b}}}_i$$\mathbf{\vec b}_i$ 和初始 edge embedding ${\overrightarrow{\mathbf{u}}}_{i,r}^{(0)}$$\mathbf{\vec u}_{i,r}^{(0)}$ 并不是针对每个节点进行训练，而是训练映射函数 $h_z(\cdot )$$h_z(\cdot)$ 和 $g_{z,r}(\cdot )$$g_{z,r}(\cdot)$，它们从原始的属性 ${\overrightarrow{\mathbf{x}}}_i$$\mathbf{\vec x}_i$ 映射到节点的 base embedding ${\overrightarrow{\mathbf{b}}}_i$$\mathbf{\vec b}_i$ 和初始 edge embedding ${\overrightarrow{\mathbf{u}}}_{i,r}^{(0)}$$\mathbf{\vec u}_{i,r}^{(0)}$ 。这可以适用于训练期间从未出现过的节点。。

1.1.4 模型学习

1. 下面我们讨论如何学习 GATNE-T 和 GATNE-I 。我们使用随机游走来生成节点序列，然后使用 SkipGram 来学习节点 embedding 。由于输入网络的每个视图都是异质的，因此我们使用 metapath-based 随机游走。

   给定网络在边类型 $r$$r$ 上的视图 ${\mathcal{G}}_r=(\mathcal{V},{\mathcal{E}}_r,\mathcal{A})$$\mathcal G_r = (\mathcal V,\mathcal E_r,\mathcal A)$，以及一个 metapath schema $\mathcal{T}:{\mathcal{V}}_1\to {\mathcal{V}}_2\to \cdots \to {\mathcal{V}}_t\to \cdots \to {\mathcal{V}}_l$$\mathcal T:\mathcal V_1\rightarrow \mathcal V_2\rightarrow\cdots\rightarrow \mathcal V_t\rightarrow\cdots\rightarrow \mathcal V_l$ ，其中 $l$$l$ 为 schema 的长度。则在随机游走的第 $t$$t$ 步的转移概率为：

   $$\begin{array}{c}p(v_j\mid v_i,\mathcal{T})=\{\begin{array}{ll}\frac{1}{|{\mathcal{N}}_{i,r}\cap {\mathcal{V}}_t|},& (v_i,v_j)\in {\mathcal{E}}_r,v_j\in {\mathcal{V}}_{t+1}\\ 0,& (v_i,v_j)\in {\mathcal{E}}_r,v_j\notin {\mathcal{V}}_{t+1}\\ 0,& (v_i,v_j)\notin {\mathcal{E}}_r\end{array}\end{array}$$

   其中 $v_i\in {\mathcal{V}}_t$$v_i\in \mathcal V_t$ ，${\mathcal{N}}_{i,r}$$\mathcal N_{i,r}$ 为节点 $v_i$$v_i$ 在边类型 $r$$r$ 上的邻域。

   基于 metapath 的随机游走策略可以确保不同类型节点之间的语义关系能够适当地融合到 SkipGram 模型中。

2. 假设随机游走在视图 ${\mathcal{G}}_r$$\mathcal G_r$ 上产生一条长度为 $l$$l$ 的随机游走序列 $\mathcal{P}=(v_{p_1},\cdots ,v_{p_l})$$\mathcal P=(v_{p_1},\cdots,v_{p_l})$，其中 $(v_{p_{t-1}},v_{p_t})\in {\mathcal{E}}_r,t=2,\cdots ,l$$(v_{p_{t-1}},v_{p_t})\in \mathcal E_r, t=2,\cdots,l$ 。定义 $v_{p_t}$$v_{p_t}$ 的上下文为：$\mathcal{C}=\{v_{p_k}\mid v_{p_k}\in \mathcal{P},|k-t|\le c,t\ne k\}$$\mathcal C = \{v_{p_{k}}\mid v_{p_k}\in \mathcal P, |k-t|\le c,t\ne k\}$ ，其中 $c$$c$ 为窗口大小。

   给定节点 $v_i$$v_i$ 及其上下文 $\mathcal{C}$$\mathcal C$，我们的目标是最小化负的对数似然：

   $$-\log P_{\theta }(\{v_j\mid v_j\in \mathcal{C}\}\mid v_i)=\sum _{v_j\in \mathcal{C}}-\log P_{\theta }(v_j\mid v_i)$$

   其中 $\theta$$\theta$ 表示所有的参数。

   和 metapath2vec 一样，我们也使用 heterogeneous softmax 函数，该函数针对节点 $v_j$$v_j$ 的节点类型进行了归一化。具体而言，给定 $v_i$$v_i$ 条件下 $v_j$$v_j$ 的概率为：

   $$P_{\theta }(v_j\mid v_i)=\frac{\exp \left({\overrightarrow{\mathbf{c}}}_j^{\mathrm{\top }}{\overrightarrow{\mathbf{v}}}_{i,r}\right)}{\sum _{k\in {\mathcal{V}}_t}\exp \left({\overrightarrow{\mathbf{c}}}_k^{\mathrm{\top }}{\overrightarrow{\mathbf{v}}}_{i,r}\right)}$$

   其中 $v_j\in {\mathcal{V}}_t$$v_j\in \mathcal V_t$， ${\overrightarrow{\mathbf{c}}}_k$$\mathbf{\vec c}_k$ 为节点 $v_k$$v_k$ 的context embedding 向量， ${\overrightarrow{\mathbf{v}}}_{i,r}$$\mathbf{\vec v}_{i,r}$ 为节点 $v_i$$v_i$ 在边类型 $r$$r$ 上的overall embedding 向量。

   这里分母仅考虑节点 $v_j$$v_j$ 所属类型的节点集合。注意，节点 $v_i$$v_i$ 的类型与 $v_j$$v_j$ 的类型可能不一致，它们的节点类型规则由 metapath 给出。

3. 最后，我们使用异质负采样（heterogeneous negative sampling ）来近似每对 $(v_i,v_j)$$(v_i,v_j)$ 的损失函数 $-\log P_{\theta }(v_j\mid v_i)$$-\log P_\theta(v_j\mid v_i)$ ：

   $$\mathcal{L}(v_i,v_j)=-\log \sigma \left({\overrightarrow{\mathbf{c}}}_j^{\mathrm{\top }}{\overrightarrow{\mathbf{v}}}_{i,r}\right)-\sum _{l=1}^L{\mathbb{E}}_{v_k\sim P_t(v)}[\log \sigma (-{\overrightarrow{\mathbf{c}}}_k^{\mathrm{\top }}{\overrightarrow{\mathbf{v}}}_{i,r})]$$

   其中：$\sigma (x)$$\sigma(x)$ 为 sigmoid 函数，$L$$L$ 为负采样系数，$v_k$$v_k$ 为从噪音分布 $P_t(v)$$P_t(v)$ 中随机采样的节点，$P_t(v)$$P_t(v)$ 是根据节点 $v_j$$v_j$ 对应类型的节点集 ${\mathcal{V}}_t$$\mathcal V_t$ 来定义的噪音分布 （noise distribution） 。

4. GATNE 算法：

   • 输入：

     • 网络 $\mathcal{G}=(\mathcal{V},\mathcal{E},\mathcal{A})$$\mathcal G=(\mathcal V,\mathcal E,\mathcal A)$

   • overall embedding 维度 $d$$d$

     • edge embedding 维度 $s$$s$

     • 学习率 $\eta$$\eta$

     • 一组 metapath schema

     • 负采样系数 $L$$L$

     • 随机游走序列长度 $l$$l$

     • 上下文窗口大小 $c$$c$

     • 平衡系数 $\alpha ,\beta$$\alpha,\beta$

     • 模型深度 $K$$K$

   • 输出：每个节点 $v_i$$v_i$ 在每个边类型 $r$$r$ 上的 overall embedding ${\overrightarrow{\mathbf{v}}}_{i,r}$$\mathbf{\vec v}_{i,r}$

   • 算法步骤：

     • 初始化模型所有的参数 $\theta$$\theta$ 。

     • 对于每个边类型 $r$$r$ ，根据 metapath schema 生成随机游走序列 ${\mathcal{P}}_r$$\mathcal P_r$ 。

     • 对每个边类型 $r$$r$ ，从随机游走序列 ${\mathcal{P}}_r$$\mathcal P_r$ 中生成训练样本 $\{(v_i,v_j,r)\}$$\{(v_i,v_j,r)\}$ 。

     • 迭代直到收敛。迭代步骤为：

       • 节点pair 对在每个边类型上迭代（即 $(v_i,v_j,r)$$(v_i,v_j,r)$） ：

         • 根据 ${\overrightarrow{\mathbf{v}}}_{i,r}={\overrightarrow{\mathbf{b}}}_i+{\alpha }_r{\mathbf{M}}_r^{\mathrm{\top }}{\mathbf{U}}_i{\overrightarrow{\mathbf{a}}}_{i,r}$$\mathbf{\vec v}_{i,r} = \mathbf{\vec b}_i+\alpha_r\mathbf M_r^\top \mathbf U_i \mathbf{\vec a}_{i,r}$ （GATNE-T） 或者 ${\overrightarrow{\mathbf{v}}}_{i,r}=h_z({\overrightarrow{\mathbf{x}}}_i)+{\alpha }_r{\mathbf{M}}_r^{\mathrm{\top }}{\mathbf{U}}_i{\overrightarrow{\mathbf{a}}}_{i,r}+{\beta }_r{\mathbf{D}}_z^{\mathrm{\top }}{\overrightarrow{\mathbf{x}}}_i$$\mathbf{\vec v}_{i,r} = h_z(\mathbf{\vec x}_i) + \alpha_r\mathbf M_r^\top\mathbf U_i\mathbf{\vec a}_{i,r} + \beta_r \mathbf D_z^\top \mathbf{\vec x}_i$ (GATNE-I) 计算 ${\overrightarrow{\mathbf{v}}}_{i,r}$$\mathbf{\vec v}_{i,r}$ 。

         • 采样 $L$$L$ 个负样本，并根据 $\mathcal{L}(v_i,v_j)=-\log \sigma \left({\overrightarrow{\mathbf{c}}}_j^{\mathrm{\top }}{\overrightarrow{\mathbf{v}}}_{i,r}\right)-\sum _{l=1}^L{\mathbb{E}}_{v_k\sim P_t(v)}[\log \sigma (-{\overrightarrow{\mathbf{c}}}_k^{\mathrm{\top }}{\overrightarrow{\mathbf{v}}}_{i,r})]$$\mathcal L(v_i,v_j) = -\log\sigma\left(\mathbf{\vec c}_j^\top \mathbf{\vec v}_{i,r}\right) - \sum_{l=1}^L \mathbb E_{v_k\sim P_t(v)}\left[\log \sigma\left(-\mathbf{\vec c}_k^\top \mathbf{\vec v}_{i,r}\right)\right]$ 计算损失函数。

         • 更新模型参数： $\theta \leftarrow \theta -\eta {\mathrm{\nabla }}_{\theta }\mathcal{L}$$\theta \leftarrow \theta-\eta\nabla_{\theta}\mathcal L$ 。

5. GATNE 算法中，基于随机游走算法的时间复杂度为 $O(n\times |\mathcal{R}|\times dL)$$O(n\times |\mathcal R|\times dL)$ ，其中 $n$$n$ 为节点数量，$|\mathcal{R}|$$|\mathcal R|$ 为边类型数量， $d$$d$ 为 overall embedding 维度， $L$$L$ 为负采样系数。

   空间复杂度为 $O(n\times (d+|\mathcal{R}|\times s))$$O(n\times (d + |\mathcal R|\times s))$ ，其中 $s$$s$ 为 edge embedding 维度。

1.2 实验

1. 这里我们首先介绍四个评估数据集和 baseline 算法的细节。我们聚焦于链接预测任务，从而对比我们的方法与其它 SOTA 方法。然后我们讨论参数敏感性、收敛性、可扩展性。最后我们在阿里巴巴推荐系统上报告了我们方法的离线 A/B test 结果。

2. 数据集：

   • Amazon Product Dataset：它是来自 Amazon 的商品评论和商品 metadata 的数据集。在我们的实验中，我们仅使用商品 metadata，包含商品属性以及商品之间的共同浏览（ co-viewing）, 共同购买（co-purchasing ）关系。商品属性包括：价格、销售排名、品牌、类目。

     数据集的节点类型集合为 $\mathcal{O}=\{\text{product}\}$$\mathcal O=\{\text{product}\}$ 。数据集的边类型集合为 $\mathcal{R}=\{\text{alsoBought},\text{alsoViewed}\}$$\mathcal R = \{\text{alsoBought},\text{alsoViewed}\}$ ，这表示两个商品分别由同一个用户共同购买或者共同浏览。数据集中的商品被划分为很多类目（ category）。如果考虑所有商品则规模庞大，因此我们选择“电子”类目的商品进行试验。但是对很多 baseline 算法来讲，电子类目的商品数量仍然过于庞大，因此我们从整个图中提取了一个连通子图（ connected subgraph ）。

   • YouTube Dataset：由 15088 个用户的各种互动行为组成的多重网络。一共包含 5 种互动类型，包括： 联系（ contact ），共享好友（shared friends），共享的订阅 （shared subscription）, 共享的订阅者（shared subscriber），共享的收藏视频（shared favorite vieoes ）。因此在该数据集中， $|\mathcal{O}|=1$$|\mathcal O| = 1$ ，以及 $|\mathcal{R}|=5$$|\mathcal R| = 5$ 。

   • Twitter Dataset：包含 2012-07-01 到 2012-07-07 之间与希格斯玻色子（Higgs boson） 的发现相关的推文。它由 450000 名Twitter 用户之间的四种关系组成，包括：转发（re-tweet），回复（ reply），提及（mention），好友/关注者 （friendship/follower） 。 因此在该数据集中， $|\mathcal{O}|=1$$|\mathcal O| = 1$ ，以及 $|\mathcal{R}|=4$$|\mathcal R| = 4$ 。

   • Alibaba Dataset：包含 user 和 item 两种类型的节点，并且 user-item 之间存在四种交互类型。交互包括：点击（click） 、添加到收藏（add-to-preference ）、加到购物车 （add-to-cart） 、以及转化（conversion ）（即购买）。因此， $\mathcal{O}=\{\text{user},\text{item}\}$$\mathcal O = \{\text{user},\text{item}\}$ ，边的类型集合 $|\mathcal{R}|=4$$|\mathcal R |= 4$ 。

     整个数据集太大无法在单台机器上评估不同方法的性能，因此我们在采样后的数据集上评估模型性能。 采样的阿里巴巴数据集称作 Alibaba-S 。另外，我们也在阿里巴巴分布式云平台上对完全的数据集进行评估，完整的数据集称作 Alibaba 。

   下表给出了这些数据集的统计信息，其中 n-types 和 e-types 分别表示顶点类型和边类型的数量。

   

   另外，由于单台机器的限制，我们用到的公共数据集是从原始公共数据集中采样的子图。下表给出了原始公共数据集的统计信息。

   

3. baseline：我们对比了以下几组baseline：

   • Network Embedding Method：包括 DeepWalk,LINE,noe2vec 。由于这些方法只能处理同质图，因此我们向它们提供具有不同类型边的独立视图，并为每个视图获取node embedding 。

   • Heterogeneous Network Embedding Method：使用 metapath2vec。当网络只有一种类型的节点时，它退化为 DeepWalk 。

   • Multiplex Heterogeneous Network Embedding Method：比较的方法包括 PMNE,MVE,MNE。

     我们将 PMNE 的三种方法分别表示为 PMNE(n),PMNE(r),PMNE(c)。MVE 使用 collaborated context embedding 并将注意力机制应用于 view-specific embedding 。MNE 对每种边类型使用一个 comment embedding 和一个 additional embedding，这些 embedding 由统一的 network embedding 共同学习。

   • Attributed Network Embedding Method：我们使用 ANRL。ANRL 使用邻域增强自编码器对节点属性信息进行建模，并使用基于属性编码器的属性感知 SkipGram 模型来捕获网络结构。

   • Attributed Multiplex Heterogeneous Network Embedding Method：使用我们提出的 GATNE 。

   另外，由于阿里巴巴数据集超过 4000 万顶点、5 亿条边，规模太大。考虑其它baseline 的 scalability，我们仅在该数据集上比较 GATNE, DeepWalk, MVE, MNE 等模型。

   对于一些没有节点属性的数据集，我们为它们生成节点特征。

4. 运行环境：我们的运行环境分为两个部分：

   • 一个是单台 Linux 服务器，其配置为 4 Xeon Platinum 8163 CPU @2.50GHz， 512G Ram，8 NVIDIA Tesla V100-SXM2-16GB 。该服务器用于训练四个较小的数据集。

   • 另一个是分布式云平台，包含数千个 worker，每两个 worker 共享一个 NVIDIA Tesla P100 GPU(16GB 显存) 。该平台用于训练最大的完整的阿里巴巴数据集。

   单机版可以分为三个部分：随机游走、模型训练和模型评估。随机游走部分参考 DeepWalk 和 metapath2vec 的相应部分来实现。模型训练部分参考 tensorflow 的 word2vec 教程来实现。模型评估部分使用了 scikit-learn 中的一些标准评估函数。模型参数通过使用 Adam 的随机梯度下降进行更新和优化。

   分布式版根据阿里巴巴分布式云平台的编程规范来实现，以最大化分布式效率。

5. 参数配置：

   • 所有方法的 base/overall embedding 维度均为 $d=200$$d=200$ ，edge embedding 维度为 $s=10$$s=10$ 。

   • 每个节点开始的随机游走序列数量为 10，随机游走序列长度为 10，上下文窗口大小为 5，负采样系数为 5 ，用于训练 SkipGram 模型的迭代数量为 100 。

   • 对于阿里巴巴数据集，metapath schema 设置为 U-I-U 和 I-U-I。其中 U 表示用户顶点，I 表示item 顶点。（metapath2vec 和 GATNE 都采用这种schema ）

   • DeepWalk：对于小数据集（公开数据集和 Alibaba-S 数据集），我们使用原作者的 Github 代码。对于阿里巴巴数据集，我们在阿里云平台上重新实现了 DeepWalk 。

   • LINE：我们使用原作者的 Github 代码。我们使用 LINE(1st+2nd) 作为 overall embedding。一阶embedding 和二阶 embedding 大小均为 100。样本量设为 10 亿。

   • node2vec：我们使用原作者的 Github 代码，其中超参数 $p=2,q=0.5$$p=2, q=0.5$ 。

   • metapath2vec：作者提供的代码仅适用于特定的数据集，无法推广到其它数据集。我们基于原始 C++ 代码，用 python 重新开发从而为任意顶点类型的网络重新实现了 metapath2vec。

     对于三个公共数据集，由于节点类型只有一种，因此 metapath2vec 退化为 DeepWalk。对于阿里巴巴数据集， metapath schema 设置为 U-I-U 和 I-U-I 。

   • PMNE：我们使用原作者的 Github 代码，其中 PMNE(c) 的层级转移概率为 0.5 。

   • MVE：我们通过 email 从原作者取到代码。每个视图的 embedding 维度为 200，每个 epoch 训练样本为 1 亿，一共训练 10 个 epoch 。

     对于阿里巴巴数据集，我们在阿里云平台上重新实现了该方法。

   • MNE：我们使用原作者的 Github 代码。对于阿里巴巴数据集，我们在阿里云平台上重新实现了该方法。

     我们将 additional embedding 维度设为 10 。

   • ANRL：我们适用来自阿里巴巴的 Github 代码。

     由于 YouTube 和 Twitter 数据集没有节点属性，因此我们为它们生成节点属性。具体而言，我们将顶点经过DeepWalk 学到的 200 维embedding 视为节点属性。

     对于 Alibba-S 和 Amazon 数据集，我们使用原始特征作为属性。

   • GATNE：

     • 最大的 epoch 设为 50。如果 ROC-AUC 指标在验证集上有 1 个训练 epoch 未能改善，则我们执行早停。

     • 对于每个边类型 $r$$r$ ，系数 ${\alpha }_r,{\beta }_r$$\alpha_r,\beta_r$ 都被设为 1 。

     • 我们使用 tensorflow 的Adam 优化器，并使用默认配置，学习率设为 0.001 。

     • 对于 A/B test 试验，我们设置 $N=50$$N=50$ （用于计算 top N 命中率）。

     • GATNE 可以采用不同的聚合函数，如均值聚合或池化聚合都达到了相似的性能。最终我们在这里使用了均值聚合。

     • 在 GATNE-I 中，我们采用 $h_z$$h_z$ 和 $g_{z,r}$$g_{z,r}$ 均为线性函数。

6. 我们通过链接预测任务来比较不同模型的效果。对于每个原始图，我们分别创建了一个验证集和测试集。

   • 验证集包含 5% 随机选择的 postive 边、5% 随机选择的 negative 边，它用于超参数选择和早停。

   • 测试集包含 10% 随机选择的 postive 边、10% 随机选择的 negative 边，它用于评估模型，并且仅在调优好的超参数下运行一次。我们使用 ROC 曲线 （ROC-AUC）、 PR 曲线（ PR-AUC）以及 F1 指标来评估。所有这些指标都在所选择的边类型之间取均值。

   我们将剔除这些 postive 边剩下的图作为训练集来训练 embedding 以及分类器。下图给出了三个公共数据集和 Alibba-S 的试验结果。

   可以看到：

   • GATNE 在所有数据集上优于各种 baseline 。

   • 由于节点属性比较少，所以 GATNE-T 在 Amazon 数据集上性能优于 GATNE-I。而阿里巴巴数据集的节点属性丰富，所以 GATNE-I 的性能最优。

   • ANRL 对于节点属性比较敏感，由于 Amazon 数据集的节点属性太少，因此其效果相对其它baseline 最差。

     另外，阿里巴巴数据集中 User 和 Item 的节点属性位于不同的空间，因此 ANRL 在 Alibaba-S 数据集上效果也很差。

   • 在 Youtube 和 Twitter 数据集上，GATNE-I 性能类似于 GATNE-T，因为这两个数据集的节点属性是 Deepwalk 得到的顶点 embedding，它是通过网络结构来生成的。

   

   进一步地，我们给出阿里巴巴数据集的实验结果。

   • GATNE 可以很好地扩展到阿里巴巴数据集上，并实现最佳效果。与之前的 state-of-the-art 算法相比，PR-AUC 提高 2.18%、ROC-AUC 提高 5.78%、F1 得分提高 5.99%。

   • 在大规模数据集中，GATNE-I 的性能超越了 GATNE-T，这表明 inductive 方法在 AMHEN 中效果更好。

   

7. 收敛性分析：我们在阿里巴巴数据集上分析了GATNE 的收敛性，如下图所示。可以看到：在大规模真实数据集上，GATNE-I 的收敛速度更快、性能更好。

   

8. 可扩展性分析：我们研究了 GATNE 的scalability 。如下图所示，我们给出了阿里巴巴数据集中，不同 worker 数量的加速比。可以看到：GATNE 在分布式平台上具有很好的可扩展性，当增加 worker 数量时训练时间显著降低。

   

9. 超参数敏感性：我们研究了不同超参数的敏感性，包括 overall embedding 维度 $d$$d$ 、edge embedding 维度 $s$$s$ 。下图给出了从给定配置 $d=200,s=10$$d=200,s=10$ 更改 $d$$d$ 或 $s$$s$ 时 GATNE 的性能。可以看到：GATNE 的性能在较大范围的 d 或 s 时相对稳定，当 d 或 s 太大或太小时性能会有降低。

   

10. 我们在阿里云分布式平台上为我们的推荐系统部署了 GATNE-I。训练数据集包含 1 亿用户和 1000 万 item， 每天有 100 亿次交互。我们用该模型为用户和商品生成 embedding 向量。对于每个用户，我们使用 kNN 和欧式距离来计算用户最有可能点击的 top N item 。我们的目标是最大化 top N 的命中率。

    推荐的 topN 列表中包含用户点击的商品，则认为是命中。命中的推荐列表占所有推荐列表的比例，则为命中率。

    在 A/B test 框架下，我们对 GATNE-I, MNE, DeepWalk 进行离线测试。结果表明：与 GATNE-I 的命中率比 MNE 提高 3.25%、比 DeepWalk 提高 24.26% 。

    这一对比没有多大实际意义，因为阿里巴巴在线推荐框架不太可能是 MNE 或者 DeepWalk 这种简单的模型。

11. 目前已有的一些公共数据集，并没有公开的训练集、验证集、测试集拆分方式。这导致在同一个数据集上进行随机拆分，最终评估的结果会不同。因此，我们无法使用先前论文中的结果。研究人员必须重新实现并运行所有的 baseline 模型，从而减少了他们对于改进自己提出的模型的关注。

    这里我们呼吁所有的研究人员提供标准化的数据集，其中包含标准化的训练集、验证集、测试集拆分。研究人员可以在标准环境下评估他们的方法，并直接比较各论文的结果。这也有助于提高研究的可重复性 （reproducibility ）。

12. 除了网络的异质性之外，网络的动态性对于网络表示学习也至关重要。捕获网络动态信息的方法有三种：

    • 可以将动态信息添加到节点属性中。如我们可以用 LSTM 之类的方法来捕获用户的动态行为。

    • 动态信息（如每次交互的时间戳）可以视为边的属性。

    • 可以考虑代表网络动态演化的几个快照。

    我们将动态属性的多重异质网络的representation learning 作为未来的工作。